#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<vector>
#include<stdio.h>
using namespace std;
#include<algorithm>
#include<vector>
using namespace std;
#include<vector>
#include<string>
#include<iostream>
using namespace std;
#include<algorithm>
class Solution
{
public:
    int singleNumber(vector<int>& nums)
    {
        sort(nums.begin(), nums.end());
        int i = 0;
        if (nums.size() == 1)
            return nums[0];
        for (i = 0;i < nums.size();++i)
        {
            if ((i - 1 >= 0 && nums[i - 1] != nums[i]) &&
                (i + 1 < nums.size() && nums[i + 1] != nums[i]))
                break;

            if (i == nums.size() - 1)
            {
                if (nums[i - 1] == nums[i])
                {
                    i = 0;
                }
                break;
            }
        }
        cout << nums[i];
        return nums[i];
    }
};
class Solution4
{
public:
    vector<string> v = { "","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz" };
    void Combinations(string& digits, int i, string str, vector<string>& myvector)
    {
        if (i == digits.size())
        {
            myvector.push_back(str);
            return;
        }

        int nums = digits[i] - '0';
        for (int j = 0;j < v[nums].size();++j)
        {
            Combinations(digits, i+1, str +v[nums][j], myvector);
        }


    }
    vector<string> letterCombinations(string digits)
    {
        vector<string> myvector;
        Combinations(digits, 0, "", myvector);
        return myvector;
    }
};
class Solution3 {
public:

    int MoreThanHalfNum_Solution(vector<int>& numbers)
    {
        if (numbers.size() == 1)
            return numbers.front();
        sort(numbers.begin(), numbers.end());
        int cnt = 1;
        int i = 1;
        for (i = 1;i < numbers.size();++i)
        {
            if (cnt * 2 > numbers.size())
                break;
            if (numbers[i] == numbers[i - 1])
                cnt++;
            else
            {
                cnt = 1;
            };
        }
        cout << numbers[i - 1];
        return numbers[i-1];

    }
};
class Solution2 {
public:
    vector<int> singleNumber(vector<int>& nums) {
        int tmp = 0;
        for (auto e : nums)
        {
            tmp ^= e;
        }
        int i = 0;
        for (i = 0;i < 32;++i)
        {
            int tmp1 = tmp;
            if ((tmp1>>=i)&1)
                break;
            
        }
        
        vector<int> v1, v2;
        for (auto e : nums)
        {
            int tmp2 = e;
            if ((tmp2 >>= i) & 1)
                v1.push_back(e);
            else
                v2.push_back(e);
        }
        int ret1 = 0, ret2 = 0;
        for (auto e : v1)
        {
            ret1 ^= e;
        }
        for (auto e : v2)
        {
            ret2 ^= e;
        }
        return { ret1,ret2 };

    }
};
class Solution1
{
public:
     vector<vector<int>> generate(int numRows)
     {
        vector<vector<int>> myvector;
        myvector.resize(numRows);
        for (int i = 0;i < numRows;++i)
        {
            myvector[i].resize(i + 1, 0);
            myvector[i][0] = myvector[i][i] = 1;
        }
        for (int i = 0;i < myvector.size();++i)
        {
            for (int j = 0;j < myvector[i].size();++j)
            {
                if (myvector[i][j] == 0)
                    myvector[i][j] = myvector[i - 1][j] + myvector[i - 1][j - 1];
            }
        }
        return myvector;
    }
};
int main()
{
    /*int arr[] = { 2,2,4,2,5,2,6,2,7 };
    vector<int> v(arr, arr+sizeof(arr)/sizeof(arr[0]));
    auto m = Solution().MoreThanHalfNum_Solution(v);
    cout << m;*/
    int arr[] = {1 };
    vector<int> v(arr, arr + sizeof(arr) / sizeof(arr[0]));
    auto m = Solution().singleNumber(v);
    return 0;
}